#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;
/*
    E->TA
    A->+TA|@
    T->FB
    B->*FB|@
    F->(E)|id
*/
struct Node
{
    string name;
    int num;
    Node *next;
};
struct Notation
{
    string name;
    int num;
    Node *p; // production
} Notation;
char NT[] = {'E', 'T', 'A', 'B', 'F'};        //non-terminal
string T[] = {"$", "+", "*", "(", ")", "id"}; //terminal
string prod[] = {"E->TA", "A->+TA|@", "T->FB", "B->*FB|@", "F->(E)|id"};
map<string, int> getChar;
string first[200];
string follow[200];
vector<string> production;
string table[20][20]; //predict table
int nti = 5, ti = 5, pi = 5;
void init()
{
    cout << "初始化" << endl;
    int j = 0;
    getChar['$' + ""] = 0;
    while (j < nti)
    {
        getChar[NT[j] + ""] = j + 1;
        j++;
    }
    j = 1;
    while (j < pi)
    {
        getChar[NT[j] + ""] = j + 30;
        j++;
    }
    j = 0;
    string pro;
    while (j < pi)
    {
        pro = "";
        pro += prod[j][0];
        for (int i = 3; i < prod[j].length(); i++)
        {
            if (prod[j][i] == '|')
            {
                production.push_back(pro);
                pro.clear();
                pro = "";
                pro += prod[j][0];
            }
            else
            {
                pro += prod[j][i];
            }
        }
        production.push_back(pro);
        j++;
    }
    // for(int i = 0; i < production.size();i++)
    //     cout << production[i] << endl;
}
bool isNonTerminal(char notation)
{
    if (notation >= 'A' && notation <= 'Z')
        return true;
    return false;
}
set<string> split(string ft)
{
    int i = 0, st = 0;
    set<string> s;
    for (i = 0; i < ft.length(); i++)
    {
        st = i;
        while (ft[i] != ',' && i < ft.length())
        {
            i++;
        }
        s.insert(ft.substr(st, i - st));
    }
    return s;
}
void union_set(set<string> &s1, set<string> &s2)
{
    set<string>::iterator i;
    for (i = s2.begin(); i != s2.end(); i++)
    {
        s1.insert(*i);
    }
}
string toString(set<string> ss)
{
    string str = "";
    set<string>::iterator i;
    for (i = ss.begin(); i != ss.end(); i++)
    {
        if (i == ss.begin())
            str += *i;
        else
            str += ',' + *i;
    }
    return str;
}
void getFirst()
{
    cout << "构造First集" << endl;
    int i, j, st, c, num;
    int flag = 1;
    char vn, v;
    set<string> ft1;
    set<string> ft2;
    string pro, ft;
    while (flag)
    {
        flag = 0;
        for (i = 0; i < production.size(); i++)
        {
            j = 1;
            vn = production[i][0];
            v = production[i][j];
            //产生式中的vt和vn一样处理，先求first，把非@加入当前非终结符的first，
            //如果first中包含@，加入当前产生式中下一个符号的first
            //如果要加入的first为空，跳出，等待下一轮添加
            //如果要加入的first是当前产生式的最后一个vt，且包含@，则把@也添加进去
            if (!isNonTerminal(v))
            {

                //截取终结符
                st = j;
                while (!isNonTerminal(production[i][j]))
                {
                    j++;
                }
                pro = production[i].substr(st, j - st);
                //得到当前非终结符的产生式
                c = getChar[vn + ""];
                ft = first[c];
                num = ft.length();
                if (ft.length() == 0)
                {
                    ft += pro;
                }
                else if (ft.find(pro) == -1)
                {
                    ft += ',' + pro;
                }
                if (num != ft.length())
                {
                    first[c] = ft;
                    flag = 1;
                }
            }
            else
            {
                //处理非终结符
                c = getChar[v + ""];
                ft = first[c];
                if (ft.length() != 0)
                {
                    ft1 = split(ft);
                    if(ft.find("@") != -1)
                    {
                        //求下一个位置的first集
                    }
                    //first中不含@
                    c = getChar[vn + ""];
                    ft = first[c];
                    ft2 = split(ft);
                    num = ft2.size();
                    union_set(ft2, ft1);
                    if (num != ft2.size())
                    {
                        ft = toString(ft2);
                        first[c] = ft;
                        flag = 1;
                    }
                }
            }
        }
    }
}
void printFirst()
{
    for (int i = 1; i <= nti; i++)
    {
        cout << "first(" << NT[i - 1] << ")={" << first[i] << "}" << endl;
    }
}
int main()
{
    // init();
    // getFirst();
    // printFirst();
    set<string> s1 = {"A", "B", "C"};
    // set<string> s2 = {"B","C","D"};
    // union_set(s1,s2);
    // set<string>::iterator i;
    // for (i = s1.begin(); i != s1.end(); i++)
    // {
    //     cout << *i << endl;
    // }
    return 0;
}